codevs 1204 寻找子串位置

传送门: http://codevs.cn/problem/1204/

Solution

俞斐然：这不是暴力吗？
罗江楠：打KMP显得咱逼格高

Code

#include<cstdio>
#include<cstring>
using namespace std;
char a[105],b[105];
int n,m,next[105],j;
int main(){
    scanf("%s",a+1);
    scanf("%s",b+1);
    n=strlen(a+1);m=strlen(b+1);
    for (int i=2;i<=m;i++){
        while (j>0&&b[i]!=b[j+1]) j=next[j];
        if (b[i]==b[j+1]) j++; next[i]=j;
    }
    j=0;
    for (int i=1;i<=n;i++){
        while (j>0&&a[i]!=b[j+1]) j=next[j];
        if (a[i]==b[j+1]) j++;
        if (j==m){printf("%d\n",i-m+1); return 0;}
    }
}